/*
    http://bhepple.freeshell.org

    Copyright (C) 2010 Bob Hepple <bhepple@freeshell.org>

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; see the file COPYING.  If not, write to
    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
    Boston, MA 02111-1307, USA.

*/

/**
 * \file tbd.h - dlist package. 
 *
 * A dlist is a double linked list of pointers, each pointing to an
 * item or 'payload' defined by the caller
 *
 * If the dlist is created (by tbd_new()) with a positive
 * 'payload_size' then this package takes care of alloc'ing and
 * free'ing the payloads (which are all the same size). Otherwise (ie
 * payload_size == 0) it's up to the caller to do it. In either case,
 * callbacks are available so that the creation of the payloads can be
 * customised. Dlists with payload_size or callbacks set are termed
 * 'managed dlists' as this package automatically creates items as
 * needed.
 *
 * eg here's a simple case where all payloads are the same and tbd is
 * allowed to do all the alloc'ing and free'ing (payload_size > 0, but
 * no callbacks):

\verbatim
 typedef struct {
     int count;
     char description[50];
 } my_payload;
 my_payload t;
 tbd_item item;

 tbd d = tbd_new(sizeof(my_payload), NULL, NULL, NULL, NULL); 
 for (i = 0; i < 500; i++) {
     t->count = i;
     snprintf(t->description, 50, "this is payload %d", i);
     item = tbd_append_new(&d); // malloc's space for the payload
     memcpy(*item, t);
 }
 t = (my_payload *)*tbd_get_index(d, 234);
 printf("%d: desc=%s\n", t->count, t->description); // gives:
 // 234: desc=this is payload 234
 tbd_free(d); // all gone
 \endverbatim

 * NB more examples in the tests directory
 * 
 * This library doesn't leak memory itself (according to valgrind
 * running on Linux) so you can make a caller watertight by using
 * tbd_free() appropriately - and by freeing anything pointed to
 * by dlist members before deleting them! The free_callback is
 * provided to make this simple.
 *
 * These routines call xcalloc, xrealloc, xfree which must be provided
 * by the caller. This provides an opportunity to handle out-of-memory
 * conditions as desired. For example, you might call calloc(1, 64000)
 * on the first call to xcalloc - then, if you run out, you could free
 * the safety buffer and longjmp out to a handler to do an emergency
 * stop or other recovery. Note: xrealloc should call xmalloc if
 * handed a NULL pointer - as on GNU libc. There's a simple
 * implementation of xmalloc etc in the unit test
 * tests/tbd_test.c. Note that the usual implementation of xmalloc
 * etc is to never return a NULL pointer eg on out-of-memory. tbd
 * does not make that assumption and allows you to let xmalloc()
 * return a NULL just like malloc().
 *
 * tbd's are thread safe provided the usual rules for using objects
 * in threads are applied by the caller - ie lock around write-access
 * to shared dlists or dlist payloads.
 *
 * Some simple checking for data corruption can be done by setting the
 * environment variable TBDLIST_CHECK:

\verbatim
TBDLIST_CHECK unset : no checking is done
TBDLIST_CHECK=1 : checking is done and error returns made
TBDLIST_CHECK=2 : checking is done and abort(3) is called
\endverbatim

 */

#ifndef _XMALLOC_H
void *xcalloc(size_t nmemb, size_t size);
void *xmalloc(size_t size);
void xfree(void *ptr);
void *xrealloc(void *ptr, size_t size);
#endif /* _XMALLOC_H */

/**
 * A dlist element - exposed so that you can traverse the list without
 * function calls:
 */
typedef struct tbd_item_s {
    void *                payload;
    struct tbd_item_s *   next;
    struct tbd_item_s *   prev;
} *tbd_item;

/**
 * Free a payload - will be called when a payload must be free'd. It
 * will be passed a pointer to the payload which is about to be freed
 * - this is the last chance to use or free anything in there. The
 * alternative is to do the payload free'ing before the tbd_free
 * call is made, just make sure all the dlist pointers are set to
 * NULL.
 *
 * \param payload [IN] payload which is about to be freed. 
 *
 * \param index [IN] index of the payload being freed
 *
 * \param caller_data [IN] pointer to the caller data provided in the
 * call to tbd_new.
 *
 * \return NULL if the callback free'd the payload, else return
 * payload. It's most important to get this right!!! Take care.
 */
typedef void *(*tbd_free_callback_t)(void *payload,
                                     void *caller_data);

/**
 * Create a new payload - this is called when a new payload needs to
 * be created. It provides an opportunity for the caller to fill out
 * values in the payload. The alternative is to do the payload
 * creations after the tbd is created.
 *
 * If a fixed size payload is defined (ie payload_size was provided in
 * the original tbd_new call) the space for the payload will
 * already have been created for you by the package. Otherwise you
 * _must_ alloc the payload in this callback and provide its address
 * in the return value.
 *
 * \param payload [IN] a pointer to the payload storage if it was
 * alloc'd by tbd (ie payload_size is known) otherwise NULL.
 *
 * \param caller_data [IN] pointer to the caller data provided in the
 * call to tbd_new.
 *
 * \return the callback should return the address of the payload. If
 * the callback encountered a problem (eg an out of memory condition)
 * it should return NULL. In this (error recovery) case tbd_new
 * will free up anything already created (possibly calling the
 * tbd_free_payload_t callback) and return NULL.
 */
typedef void *(*tbd_create_callback_t)(void *payload,
                                       void *caller_data);

/**
 * Copy a payload - this is called when a payload needs to be copied.
 * It provides an opportunity for the caller to supply values in the
 * new payload. The alternative is to do the copying after the tbd
 * is created. This callback may call the create_callback to get a new
 * item. As with create_callback, if the payload_size > 0 then a
 * zero'd memory block will have been created for you in dest_payload.
 *
 * \param dest_payload [IN] a pointer to the destination payload
 * storage if it was already alloc'd by tbd (ie payload_size is
 * known) otherwise NULL in which case the callback _must_ alloc the
 * payload and provide its address in the return value.
 *
 * \param source_payload [IN] a pointer to the source payload
 *
 * \param index [IN] the index of the payload being created.
 *
 * \param caller_data [IN] pointer to the caller data provided in the
 * call to tbd_new.
 *
 * \return the callback should return the address of the payload. If
 * the callback encountered a problem (eg an out of memory condition)
 * it should return NULL. In this (error recovery) case tbd_new
 * will free up anything already created (possibly calling the
 * tbd_free_payload_t callback) and return NULL.
 */
typedef void *(*tbd_copy_callback_t)(void *dest_payload, 
                                     void *source_payload,
                                     void *caller_data);

/**
 * The root of a dlist.
 */

#define SENTINEL 0xcafebead

typedef struct tbd_s {
    size_t                sentinel1; // FIXME: sentinels should be #ifdef DEBUG or summat
    /** size of dlist elements (0 for variable) */
    size_t                width;
    /** callbacks for payload referents (for managed payloads only). */
    tbd_free_callback_t   free_callback;
    tbd_create_callback_t create_callback;
    tbd_copy_callback_t   copy_callback;
    void *                callback_data;
    tbd_item              first;
    size_t                sentinel2;
} *tbd;

/**
 * Create a new tbd. If payload_size or callbacks are set then the
 * dlist is 'managed' by the package (as described above). 
 *
 * \param payload_size [IN] the size of each payload - if set > 0 then
 * tbd will create and destroy them as needed. Set payload_size to
 * 0 to do your own memory management - for example, if the payloads
 * are of varying size. In this case the dlist will be initially
 * filled with NULLs.
 * 
 * \param free_callback [IN] if non-NULL, this is called when a
 * payload needs to be free'd. It provides an opportunity for the
 * caller to free anything pointed to in the payload.
 * 
 * \param create_callback [IN] if non_NULL, this is called when a
 * payload need to be created. It provides an opportunity for the
 * caller to fill out the payload structure.
 *
 * \param copy_callback [IN] if non-NULL, this is when a payload needs
 * to be copied. It provides an opportunity for the caller to copy
 * anything pointed to in the payload.
 *
 * \return new tbd or NULL on error
 */
tbd tbd_new(size_t                payload_size,
            tbd_free_callback_t   free_callback,
            tbd_create_callback_t create_callback,
            tbd_copy_callback_t   copy_callback,
            void *                callback_data);

/**
 * Free a tbd object
 *
 * \param s [IN] object to free
 */
void tbd_free(tbd *s);

/**
 * Return the number of items in a tbd
 *
 * \param s [IN] tbd
 *
 * \return int length or -1 on error
 */
int tbd_get_len(const tbd d);

/**
 * Fetch the next item from the dlist.
 *
 * \param item [IN] current dlist item
 *
 * \returns the next element or NULL if no more.
 */
tbd_item tbd_get_next(const tbd_item item);

/**
 * Fetch the previous item from the dlist.
 *
 * \param item [IN] current dlist item
 *
 * \returns the next element or NULL if no more.
 */
tbd_item tbd_get_prev(const tbd_item item);

/**
 * Fetch the num'th item from the dlist.
 *
 * \param dest [IN] the dlist to search
 * 
 * \param index [IN] index into the dlist (0 for first, -1 for last)
 *
 * \returns the value of the num'th element or NULL on error (or if
 * the value is NULL!)
 */
tbd_item tbd_get_index(const tbd dest,
                       size_t    index);

/**
 * Append a new item in a list. Depending on the characteristics of
 * the dlist, this routine mallocs the payload and/or calls the
 * 'create' callback. Take care that 'location' belongs to 'dlist'.
 *
 * \param root [IN] the root of the dlist; if NULL then a new dlist is
 * created (with no callbacks and zero payload width, ie totally
 * unmanaged).
 * 
 * \param location [IN] the item to append to; if NULL, appends at the
 * start of the list.
 *
 * \returns the new tbd_item or NULL on error
 */
tbd_item tbd_append_new(tbd *    root,
                        tbd_item location);

/**
 * Callback for tbd_for_each()
 */
typedef void *(*tbd_worker_callback_t)(
    const tbd      dlist, 
    const tbd_item location,
    void *         callback_data);

/**
 * Iterate across items in the dlist making calls to a user-provided
 * callback.
 *
 * \param dlist [IN] the dlist to iterate over
 *
 * \param start_location [IN] the starting location. Put NULL and
 * 'num' >= 0 to specify the start of the list. Put NULL and 'num' < 0
 * to count from the end of the list.
 *
 * \param end_location [IN] the end location. If not NULL, then 'num'
 * is only used to indicate the direction of travel; 'num' >= 0
 * indicates forwards; 'num' < 0 indicates backwards. If end_location
 * is NULL then abs(num) indicates the number of items to process
 * (unless the end of the list is reached.
 *
 * \param num [IN] the number of items to process. Put 0 to process
 * the remaining items after 'start_location'. Put <0 to count
 * backwards. Put <0 and start_location=NULL to count back from the
 * end of the list.
 *
 * \param callback [IN] the function to call on every item
 *
 * \param callback_data [IN] user-defined data that will be passed to
 * the callback (may be NULL).
 * 
 */
tbd tbd_for_each(tbd                   dlist, 
                 tbd_item              start_location,
                 tbd_item              end_location,
                 int                   num, 
                 tbd_worker_callback_t callback,
                 void *                callback_data);

/**
 * Delete a number of items from a tbd. The 'free' callback is called
 * on every tbd_item deleted.
 *
 * \param dest [IN] tbd to be modified
 *
 * \param start_location [IN] the first item to be deleted. Put NULL
 * and 'num' >= 0 to specify the start of the list. Put NULL and 'num'
 * < 0 to count from the end of the list.
 *
 * \param end_location [IN] the end location. If not NULL, then 'num'
 * is only used to indicate the direction of travel; 'num' >= 0
 * indicates forwards; 'num' < 0 indicates backwards. If end_location
 * is NULL then abs(num) indicates the number of items to process
 * (unless the end of the list is reached.
 *
 * \param num [IN] the number of items to process. Put 0 to process
 * the remaining items after 'start_location'. Put <0 to count
 * backwards. Put <0 and start_location=NULL to count back from the
 * end of the list.
 *
 * \return NULL on error
 */
tbd tbd_delete_items(tbd      dest,
                     tbd_item start_location,
                     tbd_item end_location,
                     size_t   num);

/**
 * Chop out up to 'num' consecutive items from a dlist starting
 * at 'location'. The chopped items are returned in a new dlist with
 * the same characteristics as the original. This is equivalent to a
 * tbd_copy_items followed by a tbd_delete_items except that no
 * payload manipulations are made (eg no callbacks are called).
 *
 * \param dlist [IN/OUT] the dlist from which the items will be
 * chopped.
 *
 * \param start_location [IN] the first item to be chopped. Put NULL
 * and 'num' >= 0 to specify the start of the list. Put NULL and 'num'
 * < 0 to count from the end of the list.
 *
 * \param end_location [IN] the end location. If not NULL, then 'num'
 * is only used to indicate the direction of travel; 'num' >= 0
 * indicates forwards; 'num' < 0 indicates backwards. If end_location
 * is NULL then abs(num) indicates the number of items to process
 * (unless the end of the list is reached.
 *
 * \param num [IN] the number of items to process. Put 0 to process
 * the remaining items after 'start_location'. Put <0 to count
 * backwards. Put <0 and start_location=NULL to count back from the
 * end of the list.
 *
 * \return a new dlist containing the chopped items or NULL on
 * failure.
 */
tbd tbd_chop_items(tbd      dlist,
                   tbd_item start_location,
                   tbd_item end_location,
                   int      num);

/**
 * Copy up to 'num' consecutive items from one dlist to another. Both
 * dlists must have identical payload_size properties. The
 * copy_callback of 'dest' will be called if present.
 *
 * \param dest [IN] destination dlist (if NULL, a new dlist will be
 * created).
 *
 * \param d_location [IN] the new items will be placed after this
 * item. Put NULL to specify the start of the list.
 *
 * \param source [IN] dlist to copy from
 *
 * \param start_location [IN] the first item to be copied. Put NULL
 * and 'num' >= 0 to specify the start of the list. Put NULL and 'num'
 * < 0 to count from the end of the list.
 *
 * \param end_location [IN] the end location. If not NULL, then 'num'
 * is only used to indicate the direction of travel; 'num' >= 0
 * indicates forwards; 'num' < 0 indicates backwards. If end_location
 * is NULL then abs(num) indicates the number of items to process
 * (unless the end of the list is reached.
 *
 * \param num [IN] the number of items to process. Put 0 to process
 * the remaining items after 'start_location'. Put <0 to count
 * backwards. Put <0 and start_location=NULL to count back from the
 * end of the list.
 *
 * \return NULL on error, otherwise 'dest'
 */
tbd tbd_copy_items(tbd            dest,
                   tbd_item       d_location,
                   const tbd      source,
                   const tbd_item start_location,
                   const tbd_item end_location,
                   int            num);

/**
 * Move items from a dlist into another. The source and destination
 * dlists must be of the same type.
 *
 * \param dest [OUT] the destination dlist
 *
 * \param d_location [IN] the source will be inserted after this
 * item. Specify NULL to insert at the start.
 *
 * \param source [IN] the dlist to insert into the destination.
 *
 * \param start_location [IN] the first item to be moved. Put NULL and
 * 'num' >= 0 to specify the start of the list. Put NULL and 'num' < 0
 * to count from the end of the list.
 *
 * \param end_location [IN] the end location. If not NULL, then 'num'
 * is only used to indicate the direction of travel; 'num' >= 0
 * indicates forwards; 'num' < 0 indicates backwards. If end_location
 * is NULL then abs(num) indicates the number of items to process
 * (unless the end of the list is reached.
 *
 * \param num [IN] the number of items to process. Put 0 to process
 * the remaining items after 'start_location'. Put <0 to count
 * backwards. Put <0 and start_location=NULL to count back from the
 * end of the list.
 *
 * \return dlist or NULL on error
 */
tbd tbd_move_items(tbd            dlist,
                   tbd_item       d_location,
                   const tbd      source,
                   const tbd_item start_location,
                   const tbd_item end_location,
                   int            num);

/**
 * Push a new item onto a queue/stack FIFO/LIFO (implemented with a
 * tbd).
 *
 * \param stack [IN] pointer to a tbd - may point to NULL and a new
 * one will be created (with zero payload_size and no callbacks).
 *
 * \param payload [IN] payload to store on the stack. You should not
 * free this pointer while it is 'owned' by the tbd.
 *
 * \return the new item or NULL on error
 *
 */
tbd_item tbd_push(tbd *    stack,
                  void *   payload);

/**
 * Get the newest item from a queue/stack FIFO/LIFO
 *
 * \param stack [IN] tbd
 *
 * \return newest item, else NULL on error
 *
 */
tbd_item tbd_get_newest(const tbd stack);

/**
 * Get the oldest item from a queue/stack FIFO/LIFO
 *
 * \param stack [IN] tbd
 *
 * \return oldest item else NULL on error
 *
 */
tbd_item tbd_get_oldest(const tbd stack);

/**
 * Pop the newest item from a queue/stack FIFO/LIFO
 *
 * \param stack [IN] tbd
 *
 * \return the payload of the newest item or NULL on error.
 *
 */
void *tbd_pop(tbd stack);

/**
 * Pop the oldest item from a queue/stack FIFO/LIFO
 *
 * \param stack [IN] tbd
 *
 * \return the payload of the newest item or NULL on error.
 *
 */
void *tbd_pop_oldest(tbd stack);

#define tbd_get_first  tbd_get_oldest
#define tbd_get_last   tbd_get_newest

/**
 * A callback function used in the tbd_sort routine to compare two
 * payloads.
 *
 * \param payload1 [IN] the first payload to compare
 *
 * \param payload12 [IN] the second payload to compare
 *
 * \return It should return -1, 0 and +1 in the usual way, ie
 * according as payload1 is less than, equal to or greater than
 * payload 2.
 *
 */
typedef int(*tbd_sort_compare_t)(const void *payload1,
                                 const void *payload2);

/**
 * Sort the dlist according to a user-supplied comparison function.
 *
 * \param dlist [IN] a pointer to the dlist to be sorted.
 *
 * \param location [IN] the first item to be sorted. Use NULL for the
 * start.
 *
 * \param num [IN] the number of items to sort. Use 0 for all the
 * remaining items. Use <0 to work backwards from 'location'.
 *
 * \param compare [IN] the comparison function to be used.
 *
 * \return the (possibly new) dlist or NULL on error.
 */
tbd tbd_sort(tbd                dlist, 
             tbd_item           location,
             int                num, 
             tbd_sort_compare_t compare);
